We show, based on microscopic models, that fermionic band insulators with multiple bands and strong interband attraction are generically unstable towards nonzero momentum Cooper pairing leading to a pair density wave (PDW) superfluid state. Our first model considers a band insulating state of fermionic atoms in a three-dimensional cubic optical lattice. We show that this insulator is unstable towards an incommensurate PDW in the vicinity of a Feshbach resonance. Our second model is a two-band tight binding model relevant to electrons in solids; we show that the insulating state of this model has a PDW instability analogous to the exciton condensation instability in indirect bandgap semiconductors. We discuss relevant experimental signatures of the PDW state.